/*
 * VertexSet.h
 *
 *  Created on: Jan 24, 2014
 *      Author: ik
 */

#ifndef VERTEXSET_H_
#define VERTEXSET_H_

#include <stddef.h>
#include <cstring>
#include <iostream>
#include <iterator>
#include <stdio.h>
#include <Lista.h>

using namespace std;

#include <bitset>

#define _MAXSIZE_ 			1024
#define _MAXSIZEW_			10
#define _CPLUSPLUSBITSET_ 	bitset<_MAXSIZE_>

typedef unsigned long long int NODETYPE;	//!< bitmap node's type
#define BSIZE 		64
#define ONE 		1LL							//!< Node set to \c 1
#define MASKB 		0x3F
#define LOGB 		6
#define BYTESIZE	8
#define LOGBYTE		3
#define ALLONE		0xFFFFFFFFFFFFFFFF

#define NELEM(i) 	((i) << LOGB)			//!< Smallest element in the entry \c i of the bitmap.
#define NODEIDX(i) 	((i) >> LOGB)			//!< Node index in the bitmap of element \c i.
#define POPCOUNT(e) __builtin_popcountll(e)
#define LEAST(e) 	(__builtin_ffsll(e)-1)
#define IDXINNODE(i) ((i) & MASKB)			//!< Element index in the corresponding node of the bitmap.

class BitMapSet
{
public:
	virtual ~BitMapSet() {};

	virtual void add(int e) = 0;
	virtual void addAll() = 0;
	virtual void addAll(const BitMapSet &otro) = 0;
	virtual void addAll(const int from, const int to) = 0;
	virtual void copyAll(const BitMapSet& otro) = 0;
	virtual void copyCompl(const BitMapSet& otro) = 0;
	virtual void retainAll(const BitMapSet &otro) = 0;
	virtual void remove(int e) = 0;
	virtual void removeAll(const BitMapSet &otro) = 0;
	virtual void removeAll() = 0;
	virtual void symmetDiff(const BitMapSet &otro) = 0;
	virtual void turnToCompl() = 0;

	virtual int capacity() const = 0;
	virtual int least() const = 0;
	virtual bool contains(int e) const = 0;
	virtual bool containsInter(const BitMapSet &otro1, const BitMapSet &otro2) const = 0;
	virtual bool isSubsetOf(const BitMapSet &otro) const = 0;
	virtual bool intersects(const BitMapSet &otro) const = 0;
	virtual bool intersects(const BitMapSet &otro1, const BitMapSet &otro2) const = 0;
	virtual int size() const = 0;
	virtual bool isEmpty() const = 0;
	virtual Lista &lista() const = 0;
	virtual Lista &lista(Lista & l) const = 0;
	virtual Lista &listaDiferenca(const BitMapSet &otro, Lista & l) const = 0;
	virtual void print() const = 0;
};

class VertexSet;
class SingleNodeSetIterator;

class SingleNodeSet : public BitMapSet
{
	friend class VertexSet;

	NODETYPE* _bitset;

	SingleNodeSet(NODETYPE* s) : _bitset(s) {};

	Lista &lista(Lista & l, int offset) const;
	Lista &lista(const int from, const int to, Lista & l, int offset) const;

public:
	SingleNodeSet() : _bitset(NULL) {};
	~SingleNodeSet() {};

	void add(int e);
	void addAll();
	void addAll(const BitMapSet &otro);
	void addAll(const int from, const int to);
	void copyAll(const BitMapSet &otro);
	void copyCompl(const BitMapSet& otro);
	void retainAll(const BitMapSet &otro);
	void remove(int e);
	void removeAll(const BitMapSet &otro);
	void removeAll();
	void symmetDiff(const BitMapSet &otro);
	void turnToCompl();

	SingleNodeSetIterator begin() const;
	SingleNodeSetIterator begin(int from) const;
	SingleNodeSetIterator& end() const;

	int capacity() const;
	int least() const;
	bool contains(int e) const;
	bool containsInter(const BitMapSet &otro1, const BitMapSet &otro2) const;
	bool isSubsetOf(const BitMapSet &otro) const;
	bool intersects(const BitMapSet &otro) const;
	bool intersects(const BitMapSet &otro1, const BitMapSet &otro2) const;
	int size() const;
	bool isEmpty() const;
	Lista &lista() const;
	Lista &lista(Lista & l) const;
	Lista &lista(const int from, const int to) const;
	Lista &lista(const int from, const int to, Lista & l) const;
	Lista &listaDiferenca(const BitMapSet &otro, Lista & l) const;
	void print() const;
};

class SingleNodeSetIterator
{
	friend class SingleNodeSet;

	static SingleNodeSetIterator SingleNodeSetEnd;

protected:
	int 		_p;
	NODETYPE 	_copia;

	SingleNodeSetIterator() : _p(-1), _copia(0) {}
	SingleNodeSetIterator(NODETYPE x) : _p(-1), _copia(x) { SingleNodeSetIterator::operator ++(); }
	SingleNodeSetIterator(NODETYPE x, int i) : _p(i), _copia(x) { _copia &= (-1LL << _p); SingleNodeSetIterator::operator ++(); }
public:
	SingleNodeSetIterator(const SingleNodeSetIterator& mit) : _p(mit._p), _copia(mit._copia) {}
	SingleNodeSetIterator& operator++();
	SingleNodeSetIterator& operator++(int) {SingleNodeSetIterator& tmp(*this); SingleNodeSetIterator::operator++(); return tmp;}
	bool operator==(const SingleNodeSetIterator& rhs) {return _copia==rhs._copia && _p==rhs._p;}
	bool operator!=(const SingleNodeSetIterator& rhs) {return !SingleNodeSetIterator::operator==(rhs);}
	int& operator*() {return _p;}
};

inline SingleNodeSetIterator& SingleNodeSetIterator::operator++() {
	_p = LEAST(_copia);
	_copia &= ~(ONE << _p);

	return *this;
}

class VertexSetIterator;

class VertexSet : public BitMapSet {
	friend class VertexSetIterator;

protected:
	int 			_n;
	NODETYPE*  		_bitset;
	int 			_nw;

	VertexSet(int n, int nw, NODETYPE* bitset) : _n(n), _nw(nw), _bitset(bitset) {};

public:
	VertexSet(int n);
	VertexSet(const VertexSet &s);
	virtual ~VertexSet() {	if (_n > 0) delete[] _bitset; };

	/*
	 * \brief Crea un nuevo conjunto incambiable con los elementos de este conjunto.
	 */
	VertexSet * newUnmodifiable();
	/*
	 * \brief Crea un nuevo conjunto incambiable con los elementos de este conjunto y invalida este conjunto.
	 *
	 * Una llamada ulterior a un método de este conjunto genera un error.
	 */
	VertexSet * turnToUnmodifiable();

	/*
	 * \brief Calcula y retorna el número de elementos en este conjunto
	 */
	virtual int size() const;
	virtual bool isEmpty() const;

	bool contains(int e) const;
	bool isEqual(const BitMapSet &otro) const;
	bool containsInter(const BitMapSet &otro1, const BitMapSet &otro2) const;
	bool intersects(const BitMapSet &otro) const;
	bool intersects(const BitMapSet &otro1, const BitMapSet &otro2) const;
	bool isSubsetOf(const BitMapSet &otro) const;
	bool isDisjoint(const BitMapSet &otro) const;
	int capacity() const;
	int least() const;

	VertexSetIterator begin() const;
	VertexSetIterator begin(int from) const;
	VertexSetIterator& end() const;

	virtual void add(int e);
	virtual void addAll();
	virtual void addAll(const BitMapSet &otro);
	virtual void addAll(const int from, const int to);
	virtual void copyAll(const BitMapSet& otro);
	virtual void copyCompl(const BitMapSet& otro);
	virtual void retainAll(const BitMapSet &otro);
	virtual void remove(int e);
	virtual void removeAll(const BitMapSet &otro);
	virtual void removeAll();
	virtual void symmetDiff(const BitMapSet &otro);
	virtual void turnToCompl();

	_CPLUSPLUSBITSET_ toBitset();

	virtual Lista &lista() const;
	virtual Lista &lista(Lista & l) const;
	virtual Lista &lista(const int from, const int to) const;
	virtual Lista &lista(const int from, const int to, Lista & l) const;
	virtual Lista &listaDiferenca(const BitMapSet &otro, Lista & l) const;

	void print() const;
	SingleNodeSet& nodeView(int node, SingleNodeSet& s) const;
	VertexSet& clone();
};

class VertexSetIterator : public SingleNodeSetIterator
{
	friend class VertexSet;

	NODETYPE const *	_bitset;
	int			_offset;
	int			_node;
	int 		_last;

	static VertexSetIterator VertexSetEnd;

	VertexSetIterator() : SingleNodeSetIterator(), _bitset(NULL), _offset(0), _node(0), _last(0) {}
	VertexSetIterator(const VertexSet * s) : SingleNodeSetIterator(s->_bitset[0]), _bitset(s->_bitset), _offset(0), _node(0), _last(s->_nw-1) { if (_copia == 0 && _p < 0) operator ++(); }
	VertexSetIterator(const VertexSet * s, int from) : SingleNodeSetIterator(s->_bitset[NODEIDX(from)], IDXINNODE(from)), _bitset(s->_bitset), _offset(NELEM(NODEIDX(from))), _node(NODEIDX(from)), _last(s->_nw-1) {
		if (_copia == 0 && _p < 0) operator ++();
		else if (_p >= 0)
			_p += _offset;}
public:
	VertexSetIterator(const VertexSetIterator& mit) : SingleNodeSetIterator(mit), _bitset(mit._bitset), _offset(mit._offset), _node(mit._node), _last(mit._last) {}
	VertexSetIterator& operator++();
	VertexSetIterator& operator++(int) {VertexSetIterator& tmp(*this); operator++(); return tmp;}
	bool operator==(const VertexSetIterator& rhs) {return (_bitset==rhs._bitset && _p==rhs._p) || (_node >= _last && SingleNodeSetIterator::operator==(rhs));}
	bool operator!=(const VertexSetIterator& rhs) {return !operator==(rhs);}
	int& operator*() {return _p;}
};

inline VertexSetIterator& VertexSetIterator::operator++() {
	while (_copia == 0 && _node < _last)
	{
		_copia = _bitset[++_node];
		_offset += BSIZE;
	}
	if (_copia != 0)
	{
		int e = LEAST(_copia);
		_p = (e + _offset);
		_copia &= ~(ONE << e);
	}
	else
		_p = -1;

	return *this;
}

class UnmodifiableVertexSet : public VertexSet
{
	friend class VertexSet;

protected:
	int	_size;	//!< El número de elementos. No es calculado por este objeto.

	UnmodifiableVertexSet(const VertexSet &c) : VertexSet(c), _size(c.size()) {};
	UnmodifiableVertexSet(int n, int nw, NODETYPE* bitset, int size) : VertexSet(n, nw, bitset), _size(size) {};

public:
	~UnmodifiableVertexSet() {};

	int size() const { return _size; };
	bool isEmpty() const { return _size == 0; };

	void add(int e) { cout << "Unmodifiable set: add not allowed." << endl; throw(-1); };
	void addAll() { cout << "Unmodifiable set: addAll not allowed." << endl; throw(-1); };
	void addAll(const BitMapSet &otro) { cout << "Unmodifiable set: addAll not allowed." << endl; throw(-1); };
	void addAll(const int from, const int to) { cout << "Unmodifiable set: addAll not allowed." << endl; throw(-1); };
	void copyAll(const BitMapSet& otro) { cout << "Unmodifiable set: copyAll not allowed." << endl; throw(-1); };
	void copyCompl(const BitMapSet& otro) { cout << "Unmodifiable set: copyCompl not allowed." << endl; throw(-1); };
	void retainAll(const BitMapSet &otro) { cout << "Unmodifiable set: retainAll not allowed." << endl; throw(-1); };
	void remove(int e) { cout << "Unmodifiable set: remove not allowed" << endl; throw(-1); };
	void removeAll(const BitMapSet &otro) { cout << "Unmodifiable set: removeAll not allowed" << endl; throw(-1); };
	void removeAll() { cout << "Unmodifiable set: removeAll not allowed" << endl; throw(-1); };
	void symmetDiff(const BitMapSet &otro) { cout << "Unmodifiable set: symmetDiff not allowed" << endl; throw(-1); };
	void turnToCompl() { cout << "Unmodifiable set: turnToComp not allowed" << endl; throw(-1); };
};

inline void SingleNodeSet::add(int e)
{
	*_bitset |= (ONE << e);
}

inline void SingleNodeSet::remove(int e)
{
	*_bitset &= ~(ONE << e);
}

inline void SingleNodeSet::addAll()
{
	*_bitset = ALLONE;
}

/*!
 * If \c otro does not implement SingleNodeSet, then an error occurs.
 */
inline void SingleNodeSet::addAll(const BitMapSet &otro)
{
	*_bitset |= *((SingleNodeSet &) otro)._bitset;
}

inline void SingleNodeSet::addAll(const int from, const int to)
{
	*_bitset |= ((ALLONE << from) & (ALLONE >> (BSIZE-to)));
}

/*!
 * If \c otro does not implement SingleNodeSet, then an error occurs.
 */
inline bool SingleNodeSet::isSubsetOf(const BitMapSet &otro) const
{
	return *_bitset == (*_bitset & *((SingleNodeSet &) otro)._bitset);
}

/*!
 * If \c otro does not implement SingleNodeSet, then an error occurs.
 */
inline bool SingleNodeSet::intersects(const BitMapSet &otro) const
{
	return (*_bitset & *((SingleNodeSet &) otro)._bitset) != 0;
}

/*!
 * If \c otro does not implement SingleNodeSet, then an error occurs.
 */
inline bool SingleNodeSet::intersects(const BitMapSet &otro1, const BitMapSet &otro2) const
{
	return (*_bitset & *((SingleNodeSet &) otro1)._bitset & *((SingleNodeSet &) otro2)._bitset) != 0;
}

/*!
 * If \c otro does not implement SingleNodeSet, then an error occurs.
 */
inline void SingleNodeSet::copyAll(const BitMapSet &otro)
{
	*_bitset = *((SingleNodeSet &) otro)._bitset;
}

/*!
 * If \c otro does not implement SingleNodeSet, then an error occurs.
 */
inline void SingleNodeSet::copyCompl(const BitMapSet &otro)
{
	*_bitset = ~(*((SingleNodeSet &) otro)._bitset);
}

/*!
 * If \c otro does not implement SingleNodeSet, then an error occurs.
 */
inline void SingleNodeSet::retainAll(const BitMapSet &otro)
{
	*_bitset &= *((SingleNodeSet &) otro)._bitset;
}

inline void SingleNodeSet::turnToCompl()
{
	*_bitset = ~(*_bitset);
}

inline SingleNodeSetIterator SingleNodeSet::begin() const
{
	return SingleNodeSetIterator(*_bitset);
}

inline SingleNodeSetIterator SingleNodeSet::begin(int from) const
{
	return SingleNodeSetIterator(*_bitset, from);
}

inline SingleNodeSetIterator& SingleNodeSet::end() const
{
	return SingleNodeSetIterator::SingleNodeSetEnd;
}

inline bool SingleNodeSet::contains(int e) const
{
	return (*_bitset & (ONE << e));
}

inline bool SingleNodeSet::containsInter(const BitMapSet &otro1, const BitMapSet &otro2) const
{
	NODETYPE inter = *((SingleNodeSet &) otro1)._bitset & *((SingleNodeSet &) otro2)._bitset;
	return (*_bitset & inter) == inter;
}

inline int SingleNodeSet::capacity() const
{
	return BSIZE;
}

inline int SingleNodeSet::least() const
{
	return LEAST(*_bitset);
}

inline int SingleNodeSet::size() const
{
	return POPCOUNT(*_bitset);
}

inline void SingleNodeSet::removeAll()
{
	*_bitset = 0;
}

inline void SingleNodeSet::removeAll(const BitMapSet &otro)
{
	*_bitset &= ~(*((SingleNodeSet &) otro)._bitset);
}

inline void SingleNodeSet::symmetDiff(const BitMapSet &otro)
{
	*_bitset ^= *((SingleNodeSet &) otro)._bitset;
}

inline bool SingleNodeSet::isEmpty() const
{
	return *_bitset == 0;
}

inline Lista &SingleNodeSet::lista(const int from, const int to, Lista & l) const {
	return lista(from, to, l, 0);
}

inline Lista &SingleNodeSet::lista(const int from, const int to) const {
	return lista(from, to, *(new Lista(BSIZE)));
}

inline Lista & SingleNodeSet::lista() const
{
	return lista(*(new Lista(BSIZE)));
}

inline bool VertexSet::contains(int e) const
{
	return (_bitset[NODEIDX(e)] & (ONE << IDXINNODE(e)));
}

inline int VertexSet::capacity() const
{
	return _n;
}

inline Lista& VertexSet::lista() const
{
	return lista(*(new Lista(_n)));
}

inline Lista& VertexSet::lista(Lista & l) const
{
	return lista(0, _n, l);
}

inline Lista& VertexSet::lista(const int from, const int to) const
{
	return lista(0, _n, *(new Lista(_n)));
}

inline void VertexSet::add(int e)
{
	_bitset[NODEIDX(e)] |= (ONE << IDXINNODE(e));
}

inline void VertexSet::remove(int e)
{
	_bitset[NODEIDX(e)] &= ~(ONE << IDXINNODE(e));
}

inline void VertexSet::addAll()
{
	memset(_bitset, 0xFF, (_nw-1) << LOGBYTE);
	_bitset[_nw-1] |= (ALLONE >> (BSIZE - IDXINNODE(_n)));
}

/*!
 * If \c otro does not implement VertexSet, then an error occurs.
 */
inline void VertexSet::copyAll(const BitMapSet &otro)
{
	if (_nw < ((VertexSet &) otro)._nw)
		memcpy(_bitset, ((VertexSet &) otro)._bitset, _nw << LOGBYTE);
	else
		memcpy(_bitset, ((VertexSet &) otro)._bitset, ((VertexSet &) otro)._nw << LOGBYTE);
}

inline void VertexSet::removeAll()
{
	memset(_bitset, 0, _nw << LOGBYTE);
}

inline _CPLUSPLUSBITSET_ VertexSet::toBitset()
{
	_CPLUSPLUSBITSET_ ret(0);
	int nw = _MAXSIZEW_;
	if (nw > _nw)
		nw = _nw;
	for (int i = 0; i < nw-1; i++)
	{
		_CPLUSPLUSBITSET_ m(_bitset[i]);
		ret <<= sizeof(NODETYPE);
		ret |= m;
	}
	_CPLUSPLUSBITSET_ m(_bitset[_nw-1] ^= (ALLONE >> (BSIZE - IDXINNODE(_n))));
	ret <<= sizeof(NODETYPE);
	ret |= m;

	return ret;
}

inline VertexSet& VertexSet::clone()
{
	VertexSet * ret = new VertexSet(_n);
	ret->copyAll(*this);
	return *ret;
}

inline SingleNodeSet& VertexSet::nodeView(int node, SingleNodeSet& s) const
{
	s._bitset = _bitset+node;
	return s;
}

inline VertexSetIterator VertexSet::begin() const
{
	return VertexSetIterator(this);
}

inline VertexSetIterator VertexSet::begin(int from) const
{
	return VertexSetIterator(this, from);
}

inline VertexSetIterator& VertexSet::end() const
{
	return VertexSetIterator::VertexSetEnd;
}

#endif /* VERTEXSET_H_ */
